package P287;

import org.junit.Test;

import java.util.LinkedList;

/**
 * @Author DJ同学
 * @Date 2021/2/23 8:47
 * @Version 1.0
 * @Name 找到重复数
 * @Problem https://leetcode-cn.com/problems/find-the-duplicate-number/
 * 数组中n+1个数，数字在1-n中
 * 一个关键点就是转换成环形链表之后，fast和slow的表示
 * 参考：https://leetcode-cn.com/problems/find-the-duplicate-number/solution/kuai-man-zhi-zhen-de-jie-shi-cong-damien_undoxie-d/
 */
public class Solution {
    @Test
    public void test(){
        int duplicate = findDuplicate(new int[]{1, 2, 4, 3, 2});
        System.out.println(duplicate);
    }
    public int findDuplicate(int[] nums) {
        //nums = [1,2,4,3,2]
        /*
        转化
        * 0->1
        * 1->2
        * 2->4
        * 3->3
        * 4->2
        *
        0->1->2->4->2->2 存在环了 就变得和P142了
        * */
        //不能构造成链表 因为会发现形成了环状
        /*LinkedList<Integer> list = new LinkedList<>();
        int begin = 0;
        list.add(begin);
        while(true){
            if(list.)
            list.add(nums[begin]);
            begin = nums[begin];
        }*/
        int fast = 0;
        int slow = 0;
        while(true){//因为一定存在环
            fast = nums[nums[fast]];//走两步，套两层
            slow = nums[slow];//走一步，套一层
            if(fast==slow){//第一次相遇
                int slow2=0;
                while(slow!=slow2){
                    slow = nums[slow];
                    slow2 = nums[slow2];
                }
                return slow;
            }
        }
    }
}
